/*
题目描述：找出第 n 个丑数
丑数指的是质因数只有 2 ,3, 5的数，默认最小的丑数是 1
方法：
1. 逐个判断,存在大量无用计算，时间复杂度太高
2. 用数组将计算出来的丑数存起来，自底向上计算
根据丑数的定义可以知道，一个丑数可由另一个丑数乘2或3或5得到
将丑数从小到大存放在数组中，在每一次拓展的过程中都选择当前最小的丑数进行拓展
 */
public class E49 {
    public static void main(String[] args) {
        int n = 7;
        int res = GetUglyNumber_Solution(n);

        System.out.println(res);
    }

    public static int GetUglyNumber_Solution(int index) {
        if(index <= 0){
            return 0;
        }
        int count = 1;
        int[] res = new int[index];
        res[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        while(count < index){
            int temp = Math.min(res[p2] * 2, Math.min(res[p3] * 3, res[p5] * 5));
            if(temp == res[p2] * 2){
                p2 ++;
            }
            if(temp == res[p3] * 3){
                p3 ++;
            }
            if(temp == res[p5] * 5){
                p5 ++;
            }
            res[count++] = temp;
        }
        return res[index - 1];
    }
}
